МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет “Львівська політехніка”
Використання градієнтних методів для дослідження задач багатопараметричної оптимізації МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 5 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” ЗАТВЕРДЖЕНО На засіданні кафедри САПР Протокол № 1 від 28.08.2008 р. ЛЬВІВ 2008 Використання градієнтних методів для дослідження задач багатопараметричної оптимізації. Методичні вказівки до лабораторної роботи № 5 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” /Укл. Теслюк В. М., Андрійчук М. І. – Львів: НУ “ЛП”, 2008 р. Укладачі: Теслюк Василь Миколайович, к. т. н., доцент; Андрійчук Михайло Іванович, к. ф.-м. н., доцент. Відповідальний за випуск: Ткаченко С. П., к. т. н., доцент. Рецензенти: Каркульовський В. І., к. т. н., доцент, Стех Ю. В., к. т. н., доцент. 1. МЕТА РОБОТИ Вивчити основні градієнтні методи для розв’язування двовимірних задач оптимізації 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Градієнтні методи пошуку екстремумів Прямі методи дозволяють отримати розв’язок задачі оптимізації, використовуючи при обчисленнях тільки значення цільової функції. Роль цих методів безперечна, оскільки для багатьох практичних інженерних задач інформація про значення цільової функції є єдиною достовірною інформацією, якою володіє дослідник. З іншої сторони, при використанні навіть найефективніших прямих методів для отримання розв’язку інколи вимагається надзвичайно багато обчислень значень функції. Ця обставина поряд з цілком природнім прагненням реалізувавти можливості знаходження стаціонарних точок (тобто точок, які задовільняють необхідній умові першого порядку) приводить до необхідності розглядати методи, які грунтуються на використанні градієнта цільової функції. Надалі будемо вважати, що сама функція
, її перша похідна
, та друга похідна
існують і неперервні. Методи з використанням як перших, так і других похідних є дуже поширеними в задачах пошуку екстремумів як випуклих так і невипуклих функцій. В методах, які використовують значення першої похідної (градієнта) функції, передбачається, що компоненти градієнта можуть бути записані в аналітичному виді або з достатньо високою точністю пораховані з допомогою числових методів. Всі описані методи грунтуються на ітераційній процедурі, яка реалізується у відповідності з формулою
, (1) де
- поточне наближення до розв’язку
,
- параметр, який характеризує довжину кроку;
- напрямок пошуку в
- вимірному просторі управляючих змінних
. Метод визначення
і
на кожній ітерації пов’язаний з особливостями методу, що використовується. Як правило, вибір
здійснюється шляхом розв’язування задачі мінімізації
в напрямку
. Тому при реалізації даних методів необхідно використовувати ефективні алгоритми одновимірної мінімізації. Метод Коші Нехай в деякій точці
простору управляючих змінних необхідно визначити напрямок найшвидшого локального спуску, тобто найбільшого локального зменшення цільової функції. Розкладемо цільову функцію в околі точки
в ряд Тейлора
(2) і відкинемо члени другого порядку і вище. Зрозуміло, що локальне зменшення цільової функції визначається другим доданком, оскільки значення
фіксоване. Найбільше зменшення
визначається вибором такого напрямку в (1), якому відповідає найбільша від’ємна величина скалярного добутку, який міститься в другому доданку розкладу. Із властивості скалярного добутку слідує, що вказаний вибір забезпечується при
, (3) і другий доданок приймає вигляд
. Даний випадок відповідає найскорішому локальному спуску. Тому в основі найпростішого градієнтного методу лежить формула
, (4) де
- заданий додатній параметр. Метод має два недоліки: по-перше, виникає необхідність вибору хорошого значення
, і, по-друге, метод має повільну збіжність до точки мінімуму внаслідок малості
в околі цієї точки. Таким чином, доцільно визначати
...